Same Tree

LeetCode 100 題意

• 類別：DFS / Recursion
• 判斷兩棵二元樹是否「結構完全相同」且「節點值都相等」。
• Ex.
  Input: p = [1,2,3], q = [1,2,3]
  Output: true

thoughts

• 使用 遞迴 (DFS)：
  • 若兩個節點都為 null → 相同
  • 若一方為 null 或值不同 → 不相同
  • 否則遞迴比較 left 與 right 子樹
• 時間：O(n)
• 空間：O(h)（h 為樹高）

Kotlin

fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
    if (p == null && q == null) return true
    if (p == null || q == null) return false
    if (p.`val` != q.`val`) return false
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

Follow-up

• 如何用 迭代 (stack) 方式實作？
• 如果只允許「部分相等」（例如容忍一個節點不同），要怎麼改？
• 如何擴展到 n-ary tree（多叉樹）？